#include <dbg.h>
#include <gtest/gtest.h>

#include <numeric>
using namespace std;

#ifndef union_find
class Solution {
public:
    bool validPath(int n,
                   vector<vector<int>>& edges,
                   int source,
                   int destination) {
        vector<int> p(n);
        iota(p.begin(), p.end(), 0);  // 初始化并查集, 每个节点的父节点为自己
        dbg(p);

        vector<int> rank(n, 0);  // 初始化每个节点的秩为 0
        for (auto& e : edges) {
            int rootX = find(p, e[0]);
            int rootY = find(p, e[1]);
            dbg(rootX, rootY);
            if (rootX != rootY) {
                if (rank[rootX] > rank[rootY]) {
                    p[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    p[rootX] = rootY;
                } else {
                    p[rootY] = rootX;
                    rank[rootX]++;
                }
            }
            dbg(p);
        }
        return find(p, source) == find(p, destination);
    }

private:
    int find(vector<int>& p, int x)  // 查找节点 x 的根节点, 并进行路径压缩
    {
        if (p[x] != x) {
            p[x] = find(p, p[x]);
        }
        return p[x];
    }
};

#else
class Solution {
public:
    bool validPath(int n,
                   vector<vector<int>>& edges,
                   int source,
                   int destination) {
        vector<vector<int>> graph(n);  // 邻接表, 存储每个节点的邻节点
        for (auto& edge : edges) {
            int x = edge[0];
            int y = edge[1];
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        dbg(graph);

        vector<int> visited(n, 0);  // 标记节点是否被访问过
        visited[source] = 1;        // 标记源节点为已访问
        return dfs(source, destination, graph, visited);  // 从源节点开始 dfs
    }

private:
    bool dfs(int x,
             int destination,
             vector<vector<int>>& graph,
             vector<int>& visited) {
        if (x == destination) {  // 如果当前节点为目标节点, 则路径有效
            return true;
        }

        for (auto& y : graph[x]) {  // 遍历当前节点的所有邻节点
            if (!visited[y]) {      // 如果邻节点未被访问过
                visited[y] = 1;     // 标记为已访问
                if (dfs(y, destination, graph, visited)) {  // 递归搜索邻节点
                    return true;
                }
            }
        }

        return false;
    }
};
#endif

TEST(validPath, test1) {
    Solution s;

    vector<vector<int>> edges = {{0, 1}, {1, 2}, {2, 0}};
    EXPECT_EQ(s.validPath(3, edges, 0, 2), true);
}

TEST(validPath, test2) {
    Solution s;

    vector<vector<int>> edges = {{0, 1}, {0, 2}, {3, 5}, {5, 4}, {4, 3}};
    EXPECT_EQ(s.validPath(6, edges, 0, 5), false);
}

int main(int argc, char** argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}